/**
 * Universidad del Valle de Guatemala
 * Algoritmos y Estructura de Datos
 * Rodrigo Avelar; carné: 11192
 * programa basado de ejemplos en Java Structures de Duane A. Bailey
 */

public class ArbolHuffman {
    private BinaryTree arbol;
    private Heap heap = new Heap();
    
    /**
     * post: se genera un arbol de huffman con los nodos que pasan como parametros
     * @param list 
     */
    public ArbolHuffman(Nodo[] list){
        Nodo nodo1 = list[0];
        heap.add(nodo1);
        BinaryTree arbol1 = new BinaryTree(nodo1);
        
        Nodo nodo2 = list[1];
        heap.add(nodo2);
        BinaryTree arbol2 = new BinaryTree(nodo2);
        
        int frecuencia1 = nodo1.getFrecuencia() + nodo2.getFrecuencia();
        
        Nodo principal = new Nodo(frecuencia1);
        heap.add(principal);
        arbol = new BinaryTree(principal, arbol1, arbol2);
        
        for(int i = 2; i < list.length; i++){
        
            nodo1 = list[i];
            heap.add(nodo1);
            arbol1 = new BinaryTree(nodo1);
        
            frecuencia1 = nodo1.getFrecuencia() + frecuencia1;
            
            principal = new Nodo(frecuencia1);
            heap.add(principal);
            arbol = new BinaryTree(principal, arbol1, arbol);
        }
    }
    
    /**
     * post: se obtiene el arbol de huffman
     * @return arbol
     */
    public BinaryTree getTree(){
        return arbol;
    }
    
    /*
     * post: se asignan los codigos para cada nodo
     */
    public void setCodes(){
        String code;
        int contador = 0;
        int size = heap.size();        
        for(int i = 0; i < size; i++){            
            Nodo n = heap.remove();
            if(n.getCaracter() != null){           
                contador++;                
                if(contador==1){    // esta a la izquierda?
                    code = "0";     // se asigna 0 a los nodos izquierdos
                }
                else{
                    code = "1";
                    for(int k = 2; k < contador; k++){
                        code = code + "1"; // se asigna 1 a los nodos derechos
                    }
                    if(i != size-1){
                        code = code + "0";
                    }
                }
                // se almacena el codigo del nodo
                n.setCodigo(code);
            }
        }
    }    
}
